def max_subarray_sum(arr):
    """
    使用Kadane算法找出子数组之和的最大值
    时间复杂度: O(n)
    """
    if not arr:
        return 0
    
    max_ending_here = max_so_far = arr[0]
    
    for i in range(1, len(arr)):
        # 当前元素要么加入前面的子数组，要么重新开始
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        # 更新全局最大值
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# 测试用例
def test_max_subarray_sum():
    test_cases = [
        ([1, -2, 3, 5, -1], 8),
        ([1, -2, 3, -8, 5, 1], 6),
        ([1, -2, 3, -2, 5, 1], 7),
        ([-2, -3, -1], -1),  # 全负数情况
        ([], 0),  # 空数组
        ([5], 5)  # 单元素
    ]
    
    print("测试子数组最大和:")
    for i, (arr, expected) in enumerate(test_cases, 1):
        result = max_subarray_sum(arr)
        status = "✓" if result == expected else "✗"
        print(f"测试用例 {i}: {arr} -> 期望: {expected}, 实际: {result} {status}")

if __name__ == "__main__":
    test_max_subarray_sum()